"""
Geometric objects for collision detection, boundary definition, etc.
"""

import math


class UnknownColliderType(Exception):
    """ Raised when a shape doesn't know how to collide. """
    def __init__(self, collider):
        Exception.__init__(self)
        self.collider = collider

class Point(object):
    """ Simple 2D point. """
    x = 0.0
    y = 0.0
    def __init__(self, x=0, y=0, klass=None):
        if klass is not None:
            self.x = klass(x)
            self.y = klass(y)
        else:
            self.x = x
            self.y = y
    
    @staticmethod
    def fromVector(angle, dist):
        """ Create a new vector from an angle and magnitude. """
        deltaY = math.sin(angle) * dist
        deltaX = math.cos(angle) * dist
        return Point(deltaX, deltaY)
    
    length = property(lambda self: math.hypot(self.x, self.y) )
    tuple  = property(lambda self: (self.x, self.y) )
    pos    = property(lambda self: (int(self.x), int(self.y)) )
    loc    = property(lambda self: (int(10 * round(self.x, 1)),
                                 int(10 * round(self.y, 1)) ))
    floor  = property(lambda self: Point(math.floor(self.x),
                                        math.floor(self.y)) )
    flip   = property(lambda self: Point(self.y, self.x))
    sum    = property(lambda self: self.x + self.y)

    def round(self, places=0):
        """ Round off our coordinates to the nearest 10**-places
            and return a new Point. """
        return Point(round(self.x, places),
                     round(self.y, places))
    
    def angle(self):
        """ Our angle relative to the positive x-axis. """
        return math.atan2(self.y, self.x)
    
    def dist(self, other):
        """ The euclidean distance betwixt us and other. """
        delta = other - self
        return math.hypot(delta.x, delta.y)
    
    def __str__(self):
        return 'Pt(%s, %s)' % (self.x, self.y)
    
    def __repr__(self):
        return 'Point(%s, %s)' % (self.x, self.y)

    # Various mathemagical operations    
    def __add__(self, other):
        try:
            return Point(self.x + other.x, self.y + other.y)
        except AttributeError:
            return Point(self.x + other, self.y + other)
    
    def __sub__(self, other):
        try:
            return Point(self.x - other.x, self.y - other.y)
        except AttributeError:
            return Point(self.x - other, self.y - other)
        
    def __mul__(self, other):
        try:
            return Point(self.x * other.x, self.y * other.y)
        except AttributeError:
            return Point(self.x * other, self.y * other)
        
    def __div__(self, other):
        try:
            return Point(self.x / other.x, self.y / other.y)
        except AttributeError:
            return Point(self.x / other, self.y / other)
        
    def __abs__(self):
        return Point(abs(self.x), abs(self.y))
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    
    def __gt__(self, other):
        return (self.x > other.x) or (self.x == other.x and self.y > other.y)
    
    def __ge__(self, other):
        return (self.x > other.x) or (self.x == other.x and self.y >= other.y)
    
    def __lt__(self, other):
        return (self.x < other.x) or (self.x == other.x and self.y < other.y)
    
    def __le__(self, other):
        return (self.x < other.x) or (self.x == other.x and self.y <= other.y)
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    

class AxisAlignedBoundingBox(object):
    """
    A location defined by a isothetic rectangle.
    
    Always an exact point or larger. (i.e. max >= min).
    """
    
    (AB_CENTER,
     AB_TOPLEFT,
     AB_TOPRIGHT,
     AB_BOTTOMRIGHT,
     AB_BOTTOMLEFT) = range(5)
    
    def __init__(self, minX, minY, maxX=None, maxY=None):
        if type(minX) is Point and type(minY) is Point:
            maxX, maxY = minY.pos
            minX, minY = minX.pos
        
        self._min = Point(min(minX, maxX), min(minY, maxY))
        self._max = Point(max(minX, maxX), max(minY, maxY))
    
    def __hash__(self):
        return eval('%s+%sj' % (hash(self.min), hash(self.max)) )

    min = property(lambda self: self._min)    
    max = property(lambda self: self._max)
    bottomleft = property(lambda self: Point(self._min.x, self._max.y))
    topright = property(lambda self: Point(self._max.x, self._min.y))
    center = property(lambda self: self._min + self.radii)
    angle = property(lambda self: 0.0)
    radii = property(lambda self: self.size / 2.0)
    size = property(lambda self: self._max - self._min)

    def translate(self, delta):
        """
        Move this box by Point <delta>, and return
        the new AABB.
        """
        newMin = self._min + delta
        newMax = self._max + delta
        return AxisAlignedBoundingBox(newMin.x, newMin.y,
                                      newMax.x, newMax.y)
    
    def enumerate(self):
        """
        Yield a sequence of tuples, one for each
        integral coordinate contained herein.
        """
        for x in range(self.min.x, self.max.x+1):
            for y in range(self.min.y, self.max.y+1):
                yield (x, y)
    
    def rotate(self, quarters, about=AB_CENTER):
        """
        Rotate this box by <quarters> x 90 degrees,
        about <about>, and return the new AABB.
        """
        quarters = quarters % 4
        if quarters == 0:
            return self
        
        if about == self.AB_CENTER:
            rel = self.center
        elif about == self.AB_TOPLEFT:
            rel = self.min
        elif about == self.AB_TOPRIGHT:
            rel = self.topright
        elif about == self.AB_BOTTOMRIGHT:
            rel = self.max
        elif about == self.AB_BOTTOMLEFT:
            rel = self.bottomleft
            
        newMin = self._min - rel
        newMax = self._max - rel
        
        if 0 < quarters < 3:
            negX = Point(-1.0, 1.0)
            newMin *= negX
            newMax *= negX
            
        if quarters > 1:
            negY = Point(1.0, -1.0)
            newMin *= negY
            newMax *= negY
            
        if quarters in (1, 3):
            newMin = newMin.flip
            newMax = newMax.flip
            
        newMin += rel
        newMax += rel
        return AxisAlignedBoundingBox(newMin.x, newMin.y, newMax.x, newMax.y)

    def containsPoint(self, other):
        """
        Test for collision with the point <other>.
        """
        return (self.min.x <= other.x and
                other.x <= self.max.x and
                self.min.y <= other.y and
                other.y <= self.max.y)

    def overlapsBox(self, other):
        """
        Test for collision with the AABB <other>.
        """
        if (other.min.x > self.max.x or
            other.min.y > self.max.y or
            other.max.x < self.min.x or
            other.max.y < self.min.y):
            return False
        return True
    
    def containsBox(self, other):
        """
        Test for complete containment of AABB <other>.
        """
        if (not self.overlapsBox(other) or
            other.max.x > self.max.x or
            other.min.y < self.min.y or
            other.max.y > self.max.y or
            other.min.x < self.min.x):
            return False
        return True
    
    def collision(self, other):
        """
        Test for collision with another shape.
        """
        if hasattr(other, 'x'):
            # Point
            return self.containsPoint(other)
        elif hasattr(other, '_radii'):
            # Oriented
            return other.overlapsBox(self)
        elif hasattr(other, 'radii'):
            # Axis Aligned
            return self.overlapsBox(other)
        elif hasattr(other, 'radius'):
            # Circle
            return other.overlapsBox(self)
        
        raise UnknownColliderType(other)
        
        
    def dist(self, other):
        """
        Return the euclidean distance between
        this object and <other>.
        """
        # Note: Left and Right and Top and Bottom
        #       in the comments assume x increases to the right
        #       and y increases downward.
        #       This has no effect on the algorithm.
        #       Just pretend they're pixels on a screen.
        distance = None
        
        if hasattr(other, 'x'):

            # Depending on which of the 9 categories it falls into,
            # compare it to an edge or a corner.
            if other.x < self.min.x:

                # To the left of us
                if other.y < self.min.y:
                    # Above and left of us
                    distance =  self.min.dist(other)

                elif other.y <= self.max.y:
                    # To the left of us, between top and bottom
                    # Perpendicular distance to the left edge
                    distance =  self.min.x - other.x

                else:
                    # Below and to the left
                    distance =  self.bottomleft.dist(other)
                    
            elif other.x <= self.max.x:
                # Between the left and right
                if other.y < self.min.y:
                    # Above us
                    # Perpendicular distance to top edge
                    distance =  self.min.y - other.y
                
                elif other.y <= self.max.y:
                    # Inside us
                    distance =  0.0
                
                else:
                    # Below us
                    # Perpendicular distance to bottom edge
                    distance =  other.y - self.max.y
            
            else:
                # Above the top on the right
                if other.y < self.min.y:
                    # Above and left of us
                    distance =  self.topright.dist(other)
                
                elif other.y <= self.max.y:
                    # To the right of us, between top and bottom
                    # Perpendicular distance to right edge
                    distance =  other.x - self.max.x
                
                else:
                    # Below and to the right
                    distance =  self.max.dist(other)
                
        elif hasattr(other, 'min'):
            # Other is another BoundingBox instance
            # (or at least pretending)
            
            if other.max.x < self.min.x:
                # To the left of us
                
                if other.max.y < self.min.y:
                    # Above us
                    distance =  self.min.dist(other.max)
                
                elif other.min.y <= self.max.y:
                    # Beside us
                    # Perpendicular distance between near edges
                    distance =  self.min.x - other.max.x
                
                else:
                    # Below us
                    distance =  self.bottomleft.dist(other.topright)
                    

            elif other.min.x <= self.max.x:
                # Above, overlapping, or below us

                if other.max.y < self.min.y:
                    # Above us
                    distance =  self.min.y - other.max.y
                
                elif other.min.y <= self.max.y:
                    # Overlapping
                    distance =  0.0
                
                else:
                    # Below us
                    distance =  other.min.y - self.max.y

            
            else:
                # To the right of us

                if other.max.y < self.min.y:
                    # Above us
                    distance =  self.topright.dist(other.bottomleft)
                
                elif other.min.y <= self.max.y:
                    # Beside us
                    # Perpendicular distance between near edges
                    distance =  other.min.x - self.max.x
                
                else:
                    #Below us
                    distance =  self.max.dist(other.min)
            

        elif hasattr(other, '_radii'):
            distance = other.dist(self)
        
        if distance is None:
            raise UnknownColliderType(other)
        
        return distance
        
    def __eq__(self, other):
        return self.min == other.min and self.max == other.max

    def __str__(self):
        return "BoundingBox( %s - %s )" % (str(self.min), str(self.max))

    def __repr__(self):
        return "BoundingBox( %0.2f, %0.2f, %0.2f, %0.2f )" % (self.min.x,
                                                              self.min.y,
                                                              self.max.x,
                                                              self.max.y)


class OrientedBoundingBox(object):
    """
    A location defined by a non-isothetic rectangle
    (non-axis-aligned bounding box).
    """
    _angle = 0
    _radii = Point(0.0, 0.0)
    _center = Point(0.0, 0.0)
    
    def __init__(self, center, size, angle):
        self._center = center
        self._radii = size / 2
        self._angle = angle
        
    angle = property((lambda self: self._angle))
    radii = property((lambda self: self._radii))
    size = property((lambda self: self._radii*2))
    center = property((lambda self: self._center))

    def translation(self, other):
        """
        Return a Point object containing the
        distance (translation) between this
        object's center and the other's center.
        """
        return self._center - other.center
    
    def translate(self, delta):
        """
        Move the center box by Point <delta>, and
        return the new OBB.
        """
        return OrientedBoundingBox(self._center + delta,
                                   self.size,
                                   self._angle)
    
    def rotate(self, angle):
        """
        Return a new OBB with the same center
        and size as this object, but rotated
        by an additional <angle>.
        """
        return OrientedBoundingBox(self._center,
                                   self.size,
                                   self._angle + angle)
    
    def rotation(self, other):
        """
        Return the angular rotation difference
        between this object and <other>.
        """
        return self._angle - other.angle
    
    # Reduced version of overlapsBox 
    def containsPoint(self, other):
        """
        Test whether we collide with Point <other>.
        """
        # retrieve the relative translation
        translation = self._center - other
        # drop translation onto our X and Y vectors to make sX and sY
        distOther = abs(Point.fromVector(translation.angle() - self._angle,
                                         translation.length))
        
        # check sX (T on x)
        if (distOther.x > self._radii.x):
            return False

        # check sY (T on y)
        if (distOther.y > self._radii.y):
            return False

        return True
        
    # From Stefan Gottschalk's
    #    "Collision Queries using Oriented
    #       Bounding Boxes" (2000)
    # http://citeseer.ist.psu.edu/336883.html
    def overlapsBox(self, other):
        """
        Test whether we collide with an AABB or OBB <other>.
        """
        # retrieve the relative translation
        translation = self.translation(other)
        srad = self._radii
        orad = other.radii
        # do the cosine for dot products once.
        rot = abs(Point.fromVector(self.rotation(other), 1))

        # drop translation onto our X and Y vectors to make sX and sY
        distOther = abs(Point.fromVector(translation.angle() - self._angle,
                                         translation.length))
        
        # check sX (T on x)
        if (distOther.x > srad.x + rot.x * orad.x + rot.y * orad.y):
            return False

        # check sY (T on y)
        if (distOther.y > srad.y + rot.y * orad.x + rot.x * orad.y):
            return False

        # Check in reverse
        translation *= Point(-1.0, -1.0)
        distSelf = abs(Point.fromVector(translation.angle() - other.angle,
                                        translation.length))

        # check sX (T on x)
        if (distSelf.x > orad.x + rot.x * srad.x + rot.y * srad.y):
            return False

        # check sY (T on y)
        if (distSelf.y > orad.y + rot.y * srad.x + rot.x * srad.y):
            return False

        return True
    
    def dist(self, other):
        """
        Return the euclidean distance between
        this object and <other>.
        """
        
        if hasattr(other, 'x'):
            # Point distance.

            # retrieve the relative translation
            translation = self._center - other
            # drop translation onto our X and Y vectors to make sX and sY
            distOther = abs(Point.fromVector(translation.angle() - self._angle,
                                             translation.length))

            return max(distOther.x - self._radii.x,
                       distOther.y - self._radii.y)

        elif hasattr(other, 'radii'):
            # AABB or OBB distance.
            srad = self._radii
            orad = other.radii
            # do the cosine for dot products once.
            rot = abs(Point.fromVector(self.rotation(other), 1))
    
            # drop translation onto our X and Y vectors to make sX and sY
            translation = self.translation(other)
            distOther = abs(Point.fromVector(translation.angle() - self._angle,
                                             translation.length))
            translation *= Point(-1.0, -1.0)
            distSelf = abs(Point.fromVector(translation.angle() - other.angle,
                                            translation.length))
            
            # find the highest penetration on all projections
            return max(
                distOther.x - srad.x - rot.x * orad.x - rot.y * orad.y,
                distOther.y - srad.y - rot.y * orad.x - rot.x * orad.y,
                distSelf.x - orad.x - rot.x * srad.x - rot.y * srad.y,
                distSelf.y - orad.y - rot.y * srad.x - rot.x * srad.y
                )
        
    def collision(self, other):
        """
        Test whether this object collides with
        {Point,AABB,OBB} <other>.
        """

        if hasattr(other, 'x'):
            # Point
            return self.containsPoint(other)
        elif hasattr(other, 'radii'):
            # OBB or AABB
            return self.overlapsBox(other)
        
        elif hasattr(other, 'radius'):
            return other.overlapsBox(self)
        
        raise UnknownColliderType(other)


class BoundingCircle(object):
    
    def __init__(self, center, radius):
        self._center = center
        self._radius = radius
    
    radius = property(lambda self: self._radius)    
    center = property(lambda self: self._center)

    def collision(self, other):
        """
        Test whether this object collides with
        {Point,AABB,OBB,Circle} <other>.
        """

        if hasattr(other, 'radius'):
            return self.overlapsCircle(other)
        elif hasattr(other, 'radii'):
            return self.overlapsBox(other)
        elif hasattr(other, 'x'):
            return self.containsPoint(other)
        
        raise UnknownColliderType(other)

    def containsPoint(self, other):
        """
        Test whether this object collides with
        Point <other>.
        """
        translation = abs(self._center - other)
        if translation.length > self._radius:
            return False
        return True
    
    def overlapsCircle(self, other):
        """
        Test whether this object collides with
        BoundingCircle <other>.
        """
        # Only a single axis of separation is necessary.
        translation = abs(self._center - other.center)
        if translation.length > self._radius + other.radius:
            return False
        return True
    
    # According to:
    #   http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section3
    # we can skip the third projection if our center is closest
    # to a AABB edge, instead of an AABB vertex.  Unfortunately, 
    # that won't work for OBB's.
    def overlapsBox(self, other):
        """
        Test whether this object collides with
        {AABB,OBB} <other>.
        """
        # Three axes of separation.
        
        # retrieve the relative translation
        translation = abs(self._center - other.center)
        rot = Point.fromVector(other.angle, 1)
        
        # check sX (T on x)
        if translation.x > (other.radii * rot).sum + self._radius:
            return False

        # check sY (T on y)
        if translation.y > (other.radii * rot.flip).sum + self._radius:
            return False

        
        # check sR (T on t)
        rot = Point.fromVector(translation.angle() - other.angle,
                               1)
        if translation.length > (other.radii * rot).sum + self._radius:
            return False

        return True


#utility function for BoundingPoly
def isLeft(point, line):
    """
    Test horizontal location of a point relative to the given 
    line (or tuple of two points).
    Returns:
        >0 for point is left of the line,
        =0 for point is on the line, and
        <0 for point is right of the line.
    """
    p0, p1, p2 = line[0], line[2], point
    return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y)

class BoundingPoly(object):
    pa = ()
    def __init__(self, pa):
        """
        pa: An array of points that defines the edges of this polygon. May
        or may not have the last point be the same as the first point.
        """
        finishPoly = (pa[0] != pa[-1])
        self.pa = pa
        if self.finishPoly:
            self.pa.append(self.pa[0])
        
    def collision(self, other):
        if hasattr(other, 'radius'):
            return self.overlapsCircle(other)
        elif hasattr(other, 'radii'):
            return self.overlapsBox(other)
        elif hasattr(other, 'x'):
            return self.containsPoint(other)
        elif hasattr(other, 'pa'):
            return self.overlapsPoly(other)
        
        raise UnknownColliderType(other)
        
    def containsPoint(self, other):
        """
        Uses the winding count method, as given on:
        http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
        """
        wn = 0
        for i in range( len(self.pa) - 1 ):
            if self.pa[i].y <= other.y:
                if self.pa[i+1].y > other.y:
                    if isleft(other, (self.pa[i], self.pa[i+1]) ) > 0:
                        wn += 1
            else:
                if self.pa[i+1].y <= other.y:
                    if isLeft( other, (self.pa[i], self.pa[i+1]) ) < 0:
                        wn -= 1
        return wn != 0
    
    def overlapsCircle(self, other):
        pass
    
    def overlapsBox(self, other):
        pass
    
    def overlapsPoly(self, other):
        #http://www.geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
        #seems to have good information, but I currently do not know how and do not
        #need to figure out how to implement the suggestions given there. I think the
        #best option is a slight adaptation on psuedo-code for the Shamos-Hoey algo.
        #Currently, though, only need to intersect points.
        pass
    
if __name__ == "__main__": # pylint: block-disable-msg
    #Test the AxisAlignedBoundingBox.rotate
    abBox = AxisAlignedBoundingBox(Point(0, 0), Point(10, 10))
    #print abBox.rotate(1, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
    #print abBox.rotate(2, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
    #print abBox.rotate(3, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
    #print abBox.rotate(4, AxisAlignedBoundingBox.AB_BOTTOMLEFT)
    #print
    #
    
    # Test the BoundingCircle.collision
    obBox = OrientedBoundingBox(Point(10.0, 10.0),
                                Point(1.0,1.0), math.pi / 4)
    cBound = BoundingCircle(Point(12.0, 12.0), 2.825)
    print abBox.collision(cBound)

